package com.ds.bintree.LeetCode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Collections;

/**
 * @author Dianzhi Han
 * @version 1.0
 * @description: 迭代算法
 * @date 2022/9/20 15:22
 */
public class Num145_PostorderTraversal2 {

    List<Integer> list = new ArrayList<>();
    Deque<TreeNode> stack = new LinkedList<>(); //借助辅助栈
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null){
            return list;
        }
        TreeNode cur = root;
        while (!stack.isEmpty() || cur!=null){  //
            while (cur!=null){
                stack.push(cur);
                list.add(cur.val);
                cur = cur.right;
            }

            cur=stack.pop();
            cur = cur.left;
        }

        return list;
    }

    public List<Integer> postorderTraversal(TreeNode root) {
        list = preorderTraversal(root);
        Collections.reverse(list);
        return list;
    }
}
